/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 */

/**
 * @param {number} target
 * @param {number[]} coins
 * @return {number}
 */
function findMaxCoinIndexLessThan(target, coins) {
  let left = 0;
  let right = coins.length - 1;
  while (left <= right) {
    const middle = (left + right) >> 1;
    if (coins[middle] === target) {
      return middle;
    }
    if (coins[middle] < target) {
      if (middle === coins.length - 1 || coins[middle + 1] > target) {
        return middle;
      }
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return -1;
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  coins.sort((a, b) => a - b);
  const dp = new Array(amount + 1).fill(-1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i += 1) {
    const index = findMaxCoinIndexLessThan(i, coins);
    if (index >= 0) {
      let min = Infinity;
      for (let j = 0; j <= index; j += 1) {
        const childCount = dp[i - coins[j]];
        if (childCount >= 0) {
          const count = childCount + 1;
          if (count < min) {
            min = count;
          }
        }
      }
      if (min < Infinity) {
        dp[i] = min;
      }
    }
  }
  return dp[amount];
}

console.log(coinChange([1, 2, 5], 11) === 3);
console.log(coinChange([2], 3) === -1);
console.log(coinChange([1], 0) === 0);
